package com.wtgroup.demo.leetcode.q017_电话号码的字母组合;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/3/31 11:33
 */
public class S_DfsRecursive {

    public static void main(String[] args) {
        String[] inputs = {"23", "", "2"};
        S_DfsRecursive exe = new S_DfsRecursive();
        for (String input : inputs) {
            System.out.println(exe.letterCombinations(input));
        }
    }

    public List<String> letterCombinations(String digits) {
        // 数字 -> 字母
        List<String[]> alphaTable = new ArrayList<>();
        alphaTable.add(new String[]{""});
        alphaTable.add(new String[]{""});
        alphaTable.add(new String[]{"a", "b", "c"});
        alphaTable.add(new String[]{"d", "e", "f"});
        alphaTable.add(new String[]{"g", "h", "i"});
        alphaTable.add(new String[]{"j", "k", "l"});
        alphaTable.add(new String[]{"m", "n", "o"});
        alphaTable.add(new String[]{"p", "q", "r", "s"});
        alphaTable.add(new String[]{"t", "u", "v"});
        alphaTable.add(new String[]{"w", "x", "y", "z"});

        return m(digits, alphaTable);
    }

    private List<String> m(String digits, List<String[]> alphaTable) {
        if (digits.length()==0) {
            return Collections.emptyList();
        }

        String rest = digits.substring(1); // '2345' -> '345'
        List<String> restStrings = m(rest, alphaTable);
        int k = digits.charAt(0) - '0'; // '2' -> 2
        String[] strings = alphaTable.get(k);
        ArrayList<String> ans = new ArrayList<>();
        for (String a : strings) {
            if (!restStrings.isEmpty()) {
                for (String restString : restStrings) {
                    ans.add(a + restString);
                }
            } else {
                ans.add(a);
            }
        }

        return ans;
    }

}
